package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC676 {
    public long startExecuteTime = System.currentTimeMillis();


//    class Node {
//        public boolean setFlag = false;
//        public boolean tailFlag = false;
//        public Node[] next;
//
//        public Node() {
//            this.setFlag = true;
//            this.next = new Node[26];
//        }
//    }
//
//    class Trie {
//
//        public Node head = new Node();//tail 表示虚拟入口层
//
//        /**
//         * Initialize your data structure here.
//         */
//        public Trie() {
//            head.setFlag = true;
//        }
//
//        /**
//         * Inserts a word into the trie.
//         */
//        public void insert(String word) {
//            Node cur = this.head;
//            for (int i = 0; i < word.length(); i++) {
//                int chPos = word.charAt(i) - 'a';
//                if (cur.next[chPos] == null) {
//                    cur.next[chPos] = new Node();
//                }
//                cur = cur.next[chPos];
//            }
//
//            cur.tailFlag = true;
//        }
//
//        /**
//         * Returns if the word is in the trie.
//         */
//        public boolean searchWithOneMissMatch(Node searchHead, String word, short misMatchCount) {
//            Node cur = searchHead;
//            for (int i = 0; i < word.length(); i++) {
//                int chPos = word.charAt(i) - 'a';
//                if (cur.next[chPos] == null) {
//                    if (misMatchCount == 0) {
//                        ++misMatchCount;
//                        for (Node nextNode : cur.next) {
//                            if (null == nextNode) continue;
//                            if (searchWithOneMissMatch(nextNode, word.substring(i + 1), misMatchCount)) return true;
//                        }
//                        return false;
//                    } else return false;
//                }
//
//                for (int j = 0; j < 26; j++) {
//                    if (null == cur.next[j] || j == chPos) continue;
//                    if (searchWithOneMissMatch(cur.next[j], word.substring(i + 1), misMatchCount)) return true;
//                }
//                cur = cur.next[chPos];
//            }
//
//            return cur.tailFlag == true && misMatchCount == 1;
//        }
//    }
//
//
//    class MagicDictionary {
//        public Trie trie = new Trie();
//
//        /**
//         * Initialize your data structure here.
//         */
//        public MagicDictionary() {
//            ;
//        }
//
//        public void buildDict(String[] dictionary) {
//            for (String word : dictionary) {
//                this.trie.insert(word);
//            }
//        }
//
//        public boolean search(String searchWord) {
//            return this.trie.searchWithOneMissMatch(this.trie.head, searchWord, ((short) 0));
//        }
//    }

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 而自己的代码又具有较多bug，不具备先进性
     * @return:
     */
    class MagicDictionary {

        private Trie trie;

        /**
         * Initialize your data structure here.
         */
        public MagicDictionary() {
            trie = new Trie();
        }

        /**
         * Build a dictionary through a list of words
         */
        public void buildDict(String[] dict) {
            for (String s : dict) {
                trie.insert(s);
            }
        }

        /**
         * Returns if there is any word in the trie that equals to the given word after modifying exactly one character
         */
        public boolean search(String word) {
            return trie.search(word);
        }

        public class Trie {
            public class Node {
                boolean isWord;
                Node[] children;

                public Node(boolean isWord) {
                    this.isWord = isWord;
                    children = new Node[26];
                }
            }

            private Node root;

            public Trie() {
                this.root = new Node(false);
            }

            public void insert(String word) {
                Node node = root;
                for (char c : word.toCharArray()) {
                    int idx = c - 'a';
                    if (node.children[idx] == null) {
                        node.children[idx] = new Node(false);
                    }
                    node = node.children[idx];
                }
                node.isWord = true;
            }

            public boolean search(String word) {
                return search(word, 0, 0, root);
            }

            private boolean search(String word, int i, int misMatchCount, Node root) {
                if (misMatchCount > 1) {
                    return false;// mismatch two much.
                }
                if (i == word.length()) {
                    return misMatchCount == 1 && root.isWord;//mismatch just once and is final.
                }
                char c = word.charAt(i);
                int idx = c - 'a';
                for (int j = 0; j < 26; j++) {
                    if (root.children[j] == null) {
                        continue;
                    }
                    if (idx == j) {
                        if (search(word, i + 1, misMatchCount, root.children[j])) {
                            return true;
                        }
                    } else if (search(word, i + 1, misMatchCount + 1, root.children[j])) {
                        return true;
                    }
                }

                //如果当前字符没有后继者，并且word还没遍历完，则意味着不可能完成匹配
                return false;
            }
        }
    }


    public void run() {
        //Explanation
        MagicDictionary magicDictionary = new MagicDictionary();
        magicDictionary.buildDict(new String[]{"hello", "hallo", "leetcode"});
        System.out.println(magicDictionary.search("hello"));
        System.out.println(magicDictionary.search("hhllo"));
        System.out.println(magicDictionary.search("hell"));
        System.out.println(magicDictionary.search("leetcoded"));
    }

    public static void main(String[] args) throws Exception {
        LC676 an = new LC676();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
